A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks

Abstract

Relay node placement, which aims to connect pre-deployed sensor nodes to base stations, is essential in minimizing the costs of wireless sensor networks. In this paper, we formulate the new Node-Weighted Partial Terminal Steiner Tree Problem (NWPTSTP) for minimum-cost relay node placement in two-tiered wireless sensor networks. The objective is to minimize the sum of heterogeneous production and placement costs of relay nodes and the sum of outage probabilities of transmission routes in a routing tree simultaneously. This extends the previous work that considers the costs of relay nodes to be homogeneous. After formulating NWPTSTP for this purpose, we prove that it can be transformed to the ..